package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.entity.ListNode;
import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
// 示例 1：
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//
// 示例 2：
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//
// 示例 3：
//输入：head = []
//输出：[]
//
// 提示：
// 链表中节点的数目在范围 [0, 5 * 104] 内
// -105 <= Node.val <= 105
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
// Related Topics 链表 双指针 分治 排序 归并排序
// 👍 1831 👎 0


public class Solution148 {
	// 官方归并排序 从底向上排序 todo
	public ListNode sortList1(ListNode head) {
		if (head == null) {
			return head;
		}
		int length = 0;
		ListNode node = head;
		while (node != null) {
			length++;
			node = node.next;
		}
		int step = 1;
		while (step > 0) {
			ListNode dummyHead = head;
			while (dummyHead != null) {
				ListNode head1 = dummyHead;
				for (int j = 0; j < step && dummyHead.next != null; j++) {
					dummyHead = dummyHead.next;
				}
				ListNode head2 = dummyHead.next;
				for (int j = 0; j < step && dummyHead.next != null; j++) {
					dummyHead = dummyHead.next;
				}
				if (head2 == null) {
					head = head1;
					step = 0;
					break;
				}
				merge(head1, head2, step);
				dummyHead = dummyHead.next;
			}
			++step;
		}
		return head;
	}

	// 归并两个有序链表 //todo
	public void merge(ListNode a, ListNode b, int step) {
		for (int i = 0; i < step; i++) {
		}
	}

	// 超出时间限制
	public ListNode sortList(ListNode head) {
		ListNode a = head;
		if (a == null) return head;
		ListNode b = head.next;
		if (b == null) return head;
		a.next = null;
		while (b != null) {
			if (a.val < b.val) {
				ListNode tmp = a;
				while (tmp.next != null && tmp.next.val <= b.val) {
					tmp = tmp.next;
				}
				ListNode nb = b.next;
				ListNode tn = tmp.next;
				tmp.next = b;
				b.next = tn;
				b = nb;
			} else {
				ListNode tmp = b.next;
				b.next = a;
				a = b;
				b = tmp;
			}
		}
		return a;
	}

	public static void main(String[] args) {
		Solution148 solution = new Solution148();
		ListNode listNode = ParseUtils.ArrayToListNode("[4,2,1,3]");
		System.out.println(solution.sortList(listNode));
	}

}
